package algorithm_learn.operateArray;

public class minValue {
    //arr 整体无序
    //arr 相邻的数不相等
    //返回一个局部最小值
    public static int oneMinIndex(int[] arr){
        if(arr == null || arr.length == 0){
            return  -1;
        }
        if(arr.length == 1){
            return 0;
        }
        if(arr[0]<arr[1]){
            return 0;
        }
        int N =arr.length;
        if(arr[N-1]<arr[N-2]){
            return N-1;
        }
        int L = 0;
        int R = N-1;
        while (L<=R - 1){
            int mid = (L+R)/2;
            if (arr[mid] < arr[mid-1] && arr[mid] < arr[mid+1]){
                return mid;
            }else {
                //1 左 》 我  我  》 右
                //2 左 《 我  我 《 右
                //3 左 《 我  我 》 右
                if (arr[mid] > arr[mid - 1]){
                    // 2 3
                    R = mid - 1;
                }else {
                    L = mid + 1;
                }
            }
        }
        return arr[L] < arr[R] ? L : R;
    }
    //生成随机数组且修相连数 不相等
    public static int[] randomArray(int maxLen,int maxValue){
        int length = (int)(Math.random() * maxLen);
        int[] arr = new int[length];
        if (length > 0){
            //先确定一个值 (连续的不相同)
            arr[0] = (int)(Math.random() * maxValue);
            for (int i=1;i<length;i++){
                do {
                    arr[i] = (int)(Math.random() * maxValue);
                }while (arr[i] == arr[i - 1]);
            }
        }
        return arr;
    }
    //验证方法
    public static boolean check(int[] arr,int minIndex){
        if(arr.length == 0){
            return minIndex == -1;
        }
        //局部最小左右两边的位置
        int left = minIndex - 1;
        int right = minIndex + 1;
        //相当于判断两次
        boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true;
        boolean rightBigger = right < arr.length  ? arr[right] > arr[minIndex] : true;
        //两个都是真才是真的最低
        return leftBigger && rightBigger;
    }
    //打印
    public static void printArray(int[] arr){
        for (int num : arr){
            System.out.print(num+" ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int testTime = 100000;
        int maxValue = 20;
        int maxLen = 50;
        System.out.println("测试开始");
        for(int i =0;i<testTime;i++){
            int[] arr = randomArray(maxLen,maxValue);
            int ans = oneMinIndex(arr);
            if(!check(arr,ans)){
                printArray(arr);
                System.out.println(ans);
                break;
            }
        }
        System.out.println("测试结束");
    }
}
